#include "b_tree.h"
#include "stdlib.h"
#include "string.h"

static void b_tree_fix_up(b_tree *tree,b_tree_node *node,int bound);
static int find_lessorequal_node(b_tree_node *node,int value);
static void b_tree_merge(b_tree_node *father,int left_son_index);

int find_lessorequal_node(b_tree_node *node,int value)
{
	int i;
	for (i = 0;i<node->num_key;i++)
	{
		if (node->key_values[i]>value)
		{
			break;
		}
	}
	return i-1;
}

b_tree_node *allocate_b_tree_node()
{
	b_tree_node* res = (b_tree_node*)malloc(sizeof(b_tree_node));
	res->bLeaf = 0;
	res->num_key = 0;
	return res;
}

b_tree *b_tree_init()
{
	b_tree *res = (b_tree*)malloc(sizeof(b_tree));
	res->bound = 5;
	res->root = allocate_b_tree_node();
	res->root->bLeaf = 1;
	res->root->num_key = 0;
	return res;
}
void b_tree_split_child(b_tree_node *father,int left_son_index)
{
	
	b_tree_node *left_son = father->childs[left_son_index];
	b_tree_node *right_son = allocate_b_tree_node();
	int bound = (left_son->num_key+1)/2;
	father->bLeaf = 0;
	right_son->bLeaf = left_son->bLeaf;
	right_son->num_key = bound-1;
	memcpy(right_son->key_values,left_son->key_values + bound,(sizeof(int)*(bound-1)));
	if (!right_son->bLeaf)
	{
		memcpy(right_son->childs,left_son->childs + bound,sizeof(b_tree_node*)*bound);
	}
	left_son->num_key = bound-1;
	memcpy(father->key_values+left_son_index+1,father->key_values+left_son_index,(father->num_key-left_son_index)*sizeof(b_tree_node*));
	memcpy(father->childs+left_son_index+2,father->childs+left_son_index + 1,sizeof(int)*(father->num_key-left_son_index));
	father->num_key ++;
	father->childs[left_son_index+1] = right_son;
	father->key_values[left_son_index] = left_son->key_values[left_son->num_key];
	left_son->parent = father;
	right_son->parent = father;
}

void b_tree_insert_nonfull(b_tree_node *node,int value,int bound)
{
	int i;
	b_tree_node *to_insert;
	if (node->bLeaf)
	{
		for (i = node->num_key;i>0 && node->key_values[i-1]>value;i--)
		{
			node->key_values[i] = node->key_values[i-1];
		}
		node->key_values[i] = value;
		node->num_key ++;
	}
	else
	{
		for (i = node->num_key-1;i>=0;i--)
		{
			if (node->key_values[i]<value)
			{
				break;
			}
		}
		to_insert = node->childs[i+1];
		if (to_insert->num_key == bound*2-1)
		{
			b_tree_split_child(node,i+1);
			if (node->key_values[i+1]<value)
			{
				to_insert = node->childs[i+2];
			}
		}
		b_tree_insert_nonfull(to_insert,value,bound);
	}
}
void b_tree_insert(b_tree *tree,int value)
{
	b_tree_node *node = tree->root;
	int bound = tree->bound;
	if (node->num_key == bound*2-1)
	{
		tree->root = allocate_b_tree_node();
		tree->root->childs[0] = node;
		b_tree_split_child(tree->root,0);
		b_tree_insert_nonfull(tree->root,value,tree->bound);
	}
	else
	{
		b_tree_insert_nonfull(node,value,tree->bound);
	}
}
int b_tree_delete_max(b_tree *tree,b_tree_node *node,int bound)
{

	if (node->bLeaf)
	{
		int res;
		node->num_key--;
		res = node->key_values[node->num_key];
		if (node->num_key < bound-1)
		{
			b_tree_fix_up(tree,node,bound);
		}
		return res;
	}
	else
	{
		return b_tree_delete_max(tree,node->childs[node->num_key],bound);
	}
}
int b_tree_delete_min(b_tree *tree,b_tree_node *node,int bound)
{
	if (node->bLeaf)
	{
		int res;
		res = node->key_values[0];
		memcpy(&(node->key_values[1]),&(node->key_values[0]),sizeof(int)*node->num_key);
		b_tree_fix_up(tree,node,bound);
		return res;
	}
	else
	{
		return b_tree_delete_min(tree,node->childs[0],bound);
	}
}
void b_tree_fix_up(b_tree *tree,b_tree_node *son,int bound)
{
	b_tree_node *father = son->parent;
	int son_index;
	if (son == tree->root)
	{
		if (son->num_key == 0)
		{
			b_tree_node *temp = tree->root;
			tree->root = tree->root->childs[0];
			free(temp);
		}
		return;
	}
	son_index= find_lessorequal_node(father,son->key_values[0])+1;
	if (son->num_key >= bound-1)
	{
		return;
	}
	if (son_index > 0)
	{
		b_tree_node *son_left = father->childs[son_index-1];
		if (son_left->num_key >= bound)
		{
			int temp_value;
			memcpy(&(son->key_values[1]),son->key_values,sizeof(int)*son_left->num_key);
			memcpy(&(son->childs[1]),son->childs,sizeof(b_tree_node*)*(son->num_key+1));
			son_left->num_key--;
			son->num_key++;
			temp_value = father->key_values[son_index];
			father->key_values[son_index] = son_left->key_values[son_left->num_key];
			son->childs[0] = son_left->childs[son_left->num_key+1];
			return;
		}
	}
	if (son_index < father->num_key)
	{
		b_tree_node *son_right = father->childs[son_index+1];
		if (son_right->num_key >= bound)
		{
			son->num_key++;
			son->childs[son->num_key] = son_right->childs[0];
			son->key_values[son->num_key-1] = father->key_values[son_index];
			father->key_values[son_index] = son_right->key_values[0];
			son_right->num_key--;
			memcpy(son_right->key_values,&(son_right->key_values[1]),sizeof(int)*son_right->num_key);
			memcpy(son_right->childs,&(son_right->childs[1]),sizeof(b_tree_node*)*(son_right->num_key+1));
			return;
		}
	}
	{
		//get one key from father and merge two son
		int left_merge_index;
		b_tree_node *left_merge_node;
		if (son_index>0)
		{
			left_merge_index = son_index-1;
			left_merge_node = father->childs[left_merge_index];
		}
		else
		{
			left_merge_index = son_index;
			left_merge_node = son;
		}
		b_tree_merge(father,left_merge_index);
		if (father != tree->root)
		{
			b_tree_fix_up(tree,father,bound);
		}
		else
		{
			if (0 == father->num_key)
			{
				free(father);
				tree->root = left_merge_node;
			}
		}
	}

}
void b_tree_merge(b_tree_node *father,int left_son_index)
{
	b_tree_node *left_son,*right_son;
	left_son = father->childs[left_son_index];
	right_son = father->childs[left_son_index+1];
	father->num_key--;
	left_son->key_values[left_son->num_key] = father->key_values[left_son_index];
	//move father
	memcpy(&(father->key_values[left_son_index]),&(father->key_values[left_son_index+1]),
		sizeof(int)*(father->num_key-left_son_index));
	memcpy(&(father->childs[left_son_index+1]),&(father->childs[left_son_index+2]),
		sizeof(b_tree_node*)*(father->num_key-left_son_index));
	//move from right to left
	memcpy(&(left_son->key_values[left_son->num_key+1]),right_son->key_values,
		sizeof(int)*right_son->num_key);
	memcpy(&(left_son->childs[left_son->num_key+1]),right_son->childs,
		sizeof(b_tree_node*)*(right_son->num_key+1));
	left_son->num_key += right_son->num_key + 1;
}
void b_tree_delete_leaf(b_tree *tree,b_tree_node *father,int son_index,int value_index,int bound)
{
	b_tree_node *son = father->childs[son_index];
	son->num_key--;
	memcpy(&(son->key_values[value_index]),&(son->key_values[value_index+1]),sizeof(int)*(son->num_key-value_index));
	b_tree_fix_up(tree,son,bound);
}
void b_tree_delete_internal_node(b_tree *tree,b_tree_node *node,int value_index,int bound)
{
	b_tree_node *left_son = node->childs[value_index];
	b_tree_node *right_son = node->childs[value_index+1];
	if (left_son->num_key>bound-1)
	{
		int value = b_tree_delete_max(tree,left_son,bound);
		node->key_values[value_index] = value;
		return;
	}
	if (right_son->num_key>bound-1)
	{
		int value = b_tree_delete_min(tree,right_son,bound);
		node->key_values[value_index] = value;
		return;
	}
	b_tree_merge(node,value_index);
	left_son = node->childs[value_index];
	if (left_son->bLeaf)
	{
		b_tree_delete_leaf(tree,node,value_index,bound-1,bound);
	}
	else
	{
		b_tree_delete_internal_node(tree,left_son,bound-1,bound);
	}
	if (node->num_key <bound-1)
	{
		b_tree_fix_up(tree,node,bound);
	}

}
void b_tree_delete_node(b_tree *tree,b_tree_node *father,int son_index,int value)
{
	int bound = tree->bound;
	b_tree_node* son = father->childs[son_index];
	int i;
	for (i = 0;i<son->num_key;i++)
	{
		if (son->key_values[i]>value)
		{
			if (son->bLeaf)
			{
				return;
			}
			b_tree_delete_node(tree,son,i,value);
		}
		else if (son->key_values[i] == value)
		{
			if (son->bLeaf)
			{
				b_tree_delete_leaf(tree,father,son_index,i,bound);
			}
			else
			{
				b_tree_delete_internal_node(tree,son,i,bound);
			}
		}
	}

	if (son->bLeaf)
	{
		return;
	}
	b_tree_delete_node(tree,son,son->num_key,value);
}
void b_tree_delete(b_tree *tree,int value)
{
	int i,j;
	for (i = 0;i<tree->root->num_key;i++)
	{
		if (tree->root->key_values[i]>value)
		{
			if (tree->root->bLeaf)
			{
				return;
			}
			b_tree_delete_node(tree,tree->root,i,value);
			return;
		}
		else if (tree->root->key_values[i] == value)
		{
			if (tree->root->bLeaf)
			{
				tree->root->num_key --;
				for (j = i;j<tree->root->num_key;j++)
				{
					tree->root->key_values[j] = tree->root->key_values[j+1];
				}
				return;
			}
			else
			{
				b_tree_delete_internal_node(tree,tree->root,i,tree->bound);
				return;
			}
		}
	}
	if (tree->root->bLeaf)
	{
		return;
	}
	b_tree_delete_node(tree,tree->root,tree->root->num_key,value);
}